import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class fourSum {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> ret = new ArrayList<>();
        if (nums == null || nums.length < 4) { // 边界条件：数组长度不足4，直接返回
            return ret;
        }
        Arrays.sort(nums);
        int l = nums.length;

        for(int a=0;a < l-3; a++){
            //去重
            if(a>0 && nums[a] == nums[a-1]){
                continue;
            }
            for(int b = a+1;b < l-2; b++){
                //去重
                if(b>a+1 && nums[b] == nums[b-1]){
                    continue;
                }
                int left = b+1, right = l-1;
                long s = (long)target - nums[a] - nums[b];
                while (left < right) {
                    long sum =  (long)nums[left] +nums[right];
                    if(sum > s){
                        right--;
                    } else if(sum < s){
                        left++;
                    } else {
                        ret.add(Arrays.asList(nums[a],nums[b],nums[left],nums[right]));
                        //去重
                        while(left < right && nums[left] == nums[left+1]){
                            left++;
                        }
                        while(left < right && nums[right] == nums[right - 1]){
                            right--;
                        }
                        left++;
                        right--;
                    }
                }
            }

        }
        return ret;
    }
}
